package com.lss.e_array;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.stream.Collectors;

/**
 * @author lss
 * @description 合并区间
 * @createDate 2024/12/12-8:50
 */
public class lc_56 {
    public static void main(String[] args) {

    }

    public int[][] merge_0(int[][] intervals) {
        // 对左侧进行排序
        Arrays.sort(intervals, (p, q) -> p[0] - q[0]); // 按照左端点从小到大排序
        List<int[]> res = new ArrayList<>();
        for (int[] x : intervals) {
            int i = res.size();
            // 由于已经对左侧进行了排序
            if (i > 0 && x[0] <= res.get(i - 1)[1]) {
                res.get(i - 1)[1] = Math.max(res.get(i -1)[1],x[1]);
            }else {
                res.add(x);
            }
        }

        return res.toArray(new int[res.size()][]);
    }

    public Integer[][] merge(int[][] intervals) {
        List<List<Integer>> mergedList = new ArrayList<>();
        if (intervals == null || intervals.length == 0) {
            return new Integer[0][0]; // 处理空输入的情况
        }

        // 先将intervals转换为List<List<Integer>>，便于处理
        for (int[] interval : intervals) {
            List<Integer> list = Arrays.stream(interval).boxed().collect(Collectors.toList());
            mergedList.add(list);
        }

        // 对列表进行排序，确保区间按起始点升序排列
        mergedList.sort(Comparator.comparingInt(list -> list.get(0)));

        List<List<Integer>> resultList = new ArrayList<>();
        List<Integer> currentInterval = mergedList.get(0); // 当前正在构建的合并区间
        resultList.add(currentInterval);

        for (int i = 1; i < mergedList.size(); i++) {
            List<Integer> nextInterval = mergedList.get(i);
            if (isMerged(currentInterval, nextInterval)) {
                // 如果可以合并，则更新当前区间的结束点
                currentInterval.set(1, Math.max(currentInterval.get(1), nextInterval.get(1)));
            } else {
                // 否则，开始一个新的合并区间
                currentInterval = nextInterval;
                resultList.add(currentInterval);
            }
        }

        // 将List<List<Integer>>转换为Integer[][]
        Integer[][] resultArray = new Integer[resultList.size()][2];
        for (int i = 0; i < resultList.size(); i++) {
            resultArray[i] = resultList.get(i).toArray(new Integer[0]); // 正确转换数组类型
        }

        return resultArray;
    }

    // 假设isMerged方法已经正确定义，用于判断两个区间是否可以合并
    private boolean isMerged(List<Integer> interval1, List<Integer> interval2) {
        return interval1.get(1) >= interval2.get(0); // 例如，这样的合并逻辑
    }

}
